//
// Description: 1713. 得到子序列的最少操作次数
// Created by Loading on 2021/7/26.
//

#include <bits/stdc++.h>

using namespace std;

int minOperations(vector<int> &target, vector<int> &arr) {
    /* 求最少操作次数，只需求得 arr 与 target 的最长公共子序列长度即可 */
    /* 由于数据量过大，则使用 target 下标代替，求 arr 的最长递增子序列 */
    // 存储 target 数组中的下标
    unordered_map<int, int> pos;
    for (int i = 0; i < target.size(); ++i) {
        pos[target[i]] = i;
    }

    // 存储下标的最长递增子序列
    vector<int> maxLen_increase;
    for (auto &x : arr) {
        // 无需考虑不在 target 数组中的元素
        if (pos.count(x)) {
            int index = pos[x];
            /* 二分 + 贪心 */
            auto it = lower_bound(maxLen_increase.begin(), maxLen_increase.end(), index);
            if (it != maxLen_increase.end()) {
                *it = index;
            } else {
                maxLen_increase.emplace_back(index);
            }
        }
    }

    return (int) (target.size() - maxLen_increase.size());
}

int main() {
    vector<int> target = {6, 4, 8, 1, 3, 2};
    vector<int> arr = {4, 7, 6, 2, 3, 8, 6, 1};

    cout << minOperations(target, arr) << endl;
}